package leetcode.code0698;

import java.util.Arrays;
import java.util.TreeMap;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	public boolean canPartitionKSubsets(int[] nums, int k) {
		int sum = 0;
		TreeMap<Integer, Integer> map = new TreeMap<>();
		for (int num : nums) {
			sum += num;
			map.put(num, map.getOrDefault(num, 0) + 1);
		}
		if (sum % k != 0) {
			return false;
		}
		int avg = sum / k;
		Arrays.sort(nums);
		for (int r = nums.length - 1; r >= 0; r--) {
			int cur = nums[r];
			if (map.get(cur) != null) {
				if (map.get(cur) - 1 > 0) {
					map.put(cur, map.get(cur) - 1);
				} else {
					map.remove(cur);
				}
				int left = avg - cur;
				while (left > 0 && !map.isEmpty()) {
					Integer f = map.floorKey(left);
					if (f == null) {
						return false;
					}
					if (map.get(f) - 1 > 0) {
						map.put(f, map.get(f) - 1);
					} else {
						map.remove(f);
					}
					left -= f;
				}
				if (left == 0) {
					k--;
				} else {
					return false;
				}
			}
		}
		return k == 0;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(true, this.canPartitionKSubsets(HelpDebug.str2array3("[4,3,2,3,5,2,1]"), 4));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub
//		[10,1,10,9,6,1,9,5,9,10,7,8,5,2,10,8]
//				11
		HelpDebug.compare(false, this.canPartitionKSubsets(HelpDebug.str2array3("[10,1,10,9,6,1,9,5,9,10,7,8,5,2,10,8]"), 11));
	}

	@Override
	public void debug3() {
		HelpDebug.compare(true, this.canPartitionKSubsets(HelpDebug.str2array3("[4,4,6,2,3,8,10,2,10,7]"), 4));

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub
		HelpDebug.compare(true, this.canPartitionKSubsets(HelpDebug.str2array3("[3522,181,521,515,304,123,2512,312,922,407,146,1932,4037,2646,3871,269]"), 5));

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug4();
		so.debug2();
		so.debug3();
		so.debug1();

	}

}
